class LRUCache {
public:
    struct node{
        int key,value;
        node *left,*right;
        node(int _key,int _value):key(_key),value(_value),left(nullptr),right(nullptr){}
    }*L,*R;

    int n;
    unordered_map<int,node*> hash;

    LRUCache(int capacity) {
        n=capacity;
        L=new node(-1,-1),R=new node(-1,-1);
        L->right=R;
        R->left=L;
    }
    
    void remove(node* p)
    {
        p->right->left=p->left;
        p->left->right=p->right;
    }

    void insert(node* p)
    {
        p->right=L->right;
        p->left=L;
        L->right->left=p;
        L->right=p;
    }

    int get(int key) {
        if(!hash.count(key)) return -1;
        auto p=hash[key];
        remove(p);
        insert(p);
        return p->value;
    }
    
    void put(int key, int value) {
        if(hash.count(key))
        {
            auto p=hash[key];
            p->value=value;            
            remove(p);
            insert(p);
        }
        else
        {
            if(hash.size()==n)
            {
                auto p=R->left;
                remove(p);
                hash.erase(p->key);
                delete p;
            }
            auto p=new node(key,value);
            insert(p);
            hash[key]=p;
        }
    }
};

